1 package io.vavr.collection;
2
3 import io.vavr.Function1;
4 import io.vavr.Tuple2;
5 import io.vavr.Tuple3;
6 import io.vavr.Value;
7 import org.assertj.core.api.Assertions;
8 import org.assertj.core.api.IterableAssert;
9 import org.assertj.core.api.ObjectAssert;
10 import org.junit.Test;
11
12 import java.io.Serializable;
13 import java.util.ArrayList;
14 import java.util.Collection;
15 import java.util.Comparator;
16 import java.util.Random;
17 import java.util.function.Function;
18 import java.util.function.Supplier;
19 import java.util.stream.Collector;
20
21 import static java.util.stream.Collectors.toList;
22 import static io.vavr.Serializables.deserialize;
23 import static io.vavr.Serializables.serialize;
24
25 public class BitSetTest extends AbstractSortedSetTest {
26
27 private final static int MAX_BIT = 1_000_000;
28
29 private enum E {
30 V1, V2, V3
31 }
32
33 @Override
34 protected <T> IterableAssert<T> assertThat(Iterable<T> actual) {
35 return new IterableAssert<T>(actual) {
36 @Override
37 @SuppressWarnings("unchecked")
38 public IterableAssert<T> isEqualTo(Object obj) {
39 if (obj instanceof BitSet || actual instanceof BitSet) {
40 Assertions.assertThat(HashSet.ofAll(actual)).isEqualTo(HashSet.ofAll((Iterable<T>) obj));
41 } else {
42 super.isEqualTo(obj);
43 }
44 return this;
45 }
46 };
47 }
48
49 @Override
50 protected <T> ObjectAssert<T> assertThat(T actual) {
51 return new ObjectAssert<T>(actual) {
52 @Override
53 public ObjectAssert<T> isEqualTo(Object expected) {
54 if (actual instanceof Tuple2) {
55 final Tuple2<?, ?> t1 = (Tuple2<?, ?>) actual;
56 final Tuple2<?, ?> t2 = (Tuple2<?, ?>) expected;
57 assertThat((Iterable<?>) t1._1).isEqualTo(t2._1);
58 assertThat((Iterable<?>) t1._2).isEqualTo(t2._2);
59 return this;
60 } else if (actual instanceof Tuple3) {
61 final Tuple3<?, ?, ?> t1 = (Tuple3<?, ?, ?>) actual;
62 final Tuple3<?, ?, ?> t2 = (Tuple3<?, ?, ?>) expected;
63 assertThat((Iterable<?>) t1._1).isEqualTo(t2._1);
64 assertThat((Iterable<?>) t1._2).isEqualTo(t2._2);
65 assertThat((Iterable<?>) t1._3).isEqualTo(t2._3);
66 return this;
67 } else {
68 return super.isEqualTo(expected);
69 }
70 }
71 };
72 }
73
74 private <T> BitSet.Builder<T> bsBuilder() {
75 final Mapper<T> mapper = new Mapper<>();
76 return BitSet.withRelations(
77 (Function1<Integer, T> & Serializable) mapper::fromInt,
78 (Function1<T, Integer> & Serializable) mapper::toInt);
79 }
80
81 @Override
82 protected <T> Collector<T, ArrayList<T>, ? extends Traversable<T>> collector() {
83 return this.<T> bsBuilder().collector();
84 }
85
86 @Override
87 protected <T> BitSet<T> empty() {
88 return this.<T> bsBuilder().empty();
89 }
90
91 @Override
92 protected <T> BitSet<T> emptyWithNull() {
93 return empty();
94 }
95
96 @Override
97 protected boolean emptyShouldBeSingleton() {
98 return false;
99 }
100
101 @Override
102 protected <T> BitSet<T> of(T element) {
103 return this.<T> bsBuilder().of(element);
104 }
105
106 @Override
107 protected <T> BitSet<T> of(Comparator<? super T> comparator, T element) {
108
109 return this.<T> bsBuilder().of(element);
110 }
111
112 @SuppressWarnings("varargs")
113 @SafeVarargs
114 @Override
115 protected final <T> BitSet<T> of(Comparator<? super T> comparator, T... elements) {
116
117 return this.<T> bsBuilder().of(elements);
118 }
119
120 @SuppressWarnings("varargs")
121 @SafeVarargs
122 @Override
123 protected final <T> BitSet<T> of(T... elements) {
124 return this.<T> bsBuilder().of(elements);
125 }
126
127 @Override
128 protected boolean useIsEqualToInsteadOfIsSameAs() {
129 return true;
130 }
131
132 @Override
133 protected int getPeekNonNilPerformingAnAction() {
134 return 1;
135 }
136
137 @Override
138 protected <T> BitSet<T> ofAll(Iterable<? extends T> elements) {
139 return this.<T> bsBuilder().ofAll(elements);
140 }
141
142 @Override
143 protected <T extends Comparable<? super T>> BitSet<T> ofJavaStream(java.util.stream.Stream<? extends T> javaStream) {
144 return this.<T> bsBuilder().ofAll(javaStream);
145 }
146
147 @Override
148 protected BitSet<Boolean> ofAll(boolean... elements) {
149 return BitSet.ofAll(elements);
150 }
151
152 @Override
153 protected BitSet<Byte> ofAll(byte... elements) {
154 return BitSet.ofAll(elements);
155 }
156
157 @Override
158 protected BitSet<Character> ofAll(char... elements) {
159 return BitSet.ofAll(elements);
160 }
161
162 @Override
163 protected BitSet<Double> ofAll(double... elements) {
164 return this.<Double> bsBuilder().ofAll(Iterator.ofAll(elements));
165 }
166
167 @Override
168 protected BitSet<Float> ofAll(float... elements) {
169 return this.<Float> bsBuilder().ofAll(Iterator.ofAll(elements));
170 }
171
172 @Override
173 protected BitSet<Integer> ofAll(int... elements) {
174 return BitSet.ofAll(elements);
175 }
176
177 @Override
178 protected BitSet<Long> ofAll(long... elements) {
179 return BitSet.ofAll(elements);
180 }
181
182 @Override
183 protected BitSet<Short> ofAll(short... elements) {
184 return BitSet.ofAll(elements);
185 }
186
187 @Override
188 protected <T> BitSet<T> tabulate(int n, Function<? super Integer, ? extends T> f) {
189 return this.<T> bsBuilder().tabulate(n, f);
190 }
191
192 @Override
193 protected <T> BitSet<T> fill(int n, Supplier<? extends T> s) {
194 return this.<T> bsBuilder().fill(n, s);
195 }
196
197 @Override
198 protected BitSet<Character> range(char from, char toExclusive) {
199 return BitSet.range(from, toExclusive);
200 }
201
202 @Override
203 protected BitSet<Character> rangeBy(char from, char toExclusive, int step) {
204 return BitSet.rangeBy(from, toExclusive, step);
205 }
206
207 @Override
208 protected BitSet<Double> rangeBy(double from, double toExclusive, double step) {
209 return this.<Double> bsBuilder().ofAll(Iterator.rangeBy(from, toExclusive, step));
210 }
211
212 private static boolean isBadRange(int a, int b) {
213 return a < 0 || b < 0 || a > MAX_BIT || b > MAX_BIT;
214 }
215
216 private static boolean isBadRange(long a, long b) {
217 return a < 0 || b < 0 || a > MAX_BIT || b > MAX_BIT;
218 }
219
220 @Override
221 protected BitSet<Integer> range(int from, int toExclusive) {
222 if (isBadRange(from, toExclusive)) {
223 return this.<Integer> bsBuilder().ofAll(Iterator.range(from, toExclusive));
224 } else {
225 return BitSet.range(from, toExclusive);
226 }
227 }
228
229 @Override
230 protected BitSet<Integer> rangeBy(int from, int toExclusive, int step) {
231 if (isBadRange(from, toExclusive)) {
232 return this.<Integer> bsBuilder().ofAll(Iterator.rangeBy(from, toExclusive, step));
233 } else {
234 return BitSet.rangeBy(from, toExclusive, step);
235 }
236 }
237
238 @Override
239 protected BitSet<Long> range(long from, long toExclusive) {
240 if (isBadRange(from, toExclusive)) {
241 return this.<Long> bsBuilder().ofAll(Iterator.range(from, toExclusive));
242 } else {
243 return BitSet.range(from, toExclusive);
244 }
245 }
246
247 @Override
248 protected BitSet<Long> rangeBy(long from, long toExclusive, long step) {
249 if (isBadRange(from, toExclusive)) {
250 return this.<Long> bsBuilder().ofAll(Iterator.rangeBy(from, toExclusive, step));
251 } else {
252 return BitSet.rangeBy(from, toExclusive, step);
253 }
254 }
255
256 @Override
257 protected BitSet<Character> rangeClosed(char from, char toInclusive) {
258 return BitSet.rangeClosed(from, toInclusive);
259 }
260
261 @Override
262 protected BitSet<Character> rangeClosedBy(char from, char toInclusive, int step) {
263 return BitSet.rangeClosedBy(from, toInclusive, step);
264 }
265
266 @Override
267 protected BitSet<Double> rangeClosedBy(double from, double toInclusive, double step) {
268 return this.<Double> bsBuilder().ofAll(Iterator.rangeClosedBy(from, toInclusive, step));
269 }
270
271 @Override
272 protected BitSet<Integer> rangeClosed(int from, int toInclusive) {
273 if (isBadRange(from, toInclusive)) {
274 return this.<Integer> bsBuilder().ofAll(Iterator.rangeClosed(from, toInclusive));
275 } else {
276 return BitSet.rangeClosed(from, toInclusive);
277 }
278 }
279
280 @Override
281 protected BitSet<Integer> rangeClosedBy(int from, int toInclusive, int step) {
282 if (isBadRange(from, toInclusive)) {
283 return this.<Integer> bsBuilder().ofAll(Iterator.rangeClosedBy(from, toInclusive, step));
284 } else {
285 return BitSet.rangeClosedBy(from, toInclusive, step);
286 }
287 }
288
289 @Override
290 protected BitSet<Long> rangeClosed(long from, long toInclusive) {
291 if (isBadRange(from, toInclusive)) {
292 return this.<Long> bsBuilder().ofAll(Iterator.rangeClosed(from, toInclusive));
293 } else {
294 return BitSet.rangeClosed(from, toInclusive);
295 }
296 }
297
298 @Override
299 protected BitSet<Long> rangeClosedBy(long from, long toInclusive, long step) {
300 if (isBadRange(from, toInclusive)) {
301 return this.<Long> bsBuilder().ofAll(Iterator.rangeClosedBy(from, toInclusive, step));
302 } else {
303 return BitSet.rangeClosedBy(from, toInclusive, step);
304 }
305 }
306
307
308
309 @Test
310 public void testBitSet1() {
311 BitSet<Integer> bs = BitSet.empty();
312
313 bs = bs.add(2);
314 assertThat(bs.head()).isEqualTo(2);
315 assertThat(bs.length()).isEqualTo(1);
316
317 bs = bs.add(4);
318 assertThat(bs.head()).isEqualTo(2);
319 assertThat(bs.length()).isEqualTo(2);
320
321 bs = bs.remove(2);
322 assertThat(bs.head()).isEqualTo(4);
323 assertThat(bs.contains(2)).isFalse();
324 assertThat(bs.length()).isEqualTo(1);
325
326 bs = bs.remove(4);
327 assertThat(bs.isEmpty()).isTrue();
328 assertThat(bs.length()).isEqualTo(0);
329 }
330
331 @Test
332 public void testBitSet2() {
333 BitSet<Integer> bs = BitSet.empty();
334
335 bs = bs.add(2);
336 assertThat(bs.head()).isEqualTo(2);
337 assertThat(bs.add(2)).isSameAs(bs);
338 assertThat(bs.length()).isEqualTo(1);
339
340 bs = bs.add(70);
341 assertThat(bs.head()).isEqualTo(2);
342 assertThat(bs.add(2)).isSameAs(bs);
343 assertThat(bs.add(70)).isSameAs(bs);
344 assertThat(bs.length()).isEqualTo(2);
345
346 bs = bs.remove(2);
347 assertThat(bs.head()).isEqualTo(70);
348 assertThat(bs.contains(2)).isFalse();
349 assertThat(bs.length()).isEqualTo(1);
350
351 bs = bs.remove(70);
352 assertThat(bs.isEmpty()).isTrue();
353 assertThat(bs.length()).isEqualTo(0);
354
355 bs = bs.add(2);
356 bs = bs.add(70);
357 bs = bs.add(3);
358 assertThat(bs.length()).isEqualTo(3);
359 bs = bs.add(71);
360 assertThat(bs.length()).isEqualTo(4);
361 bs = bs.add(701);
362 assertThat(bs.length()).isEqualTo(5);
363
364 }
365
366 @Test
367 public void testBitSetN() {
368 BitSet<Integer> bs = BitSet.empty();
369
370 bs = bs.add(2);
371 assertThat(bs.head()).isEqualTo(2);
372
373 bs = bs.add(700);
374 assertThat(bs.head()).isEqualTo(2);
375 assertThat(bs.add(2)).isSameAs(bs);
376 assertThat(bs.add(700)).isSameAs(bs);
377
378 bs = bs.remove(2);
379 assertThat(bs.head()).isEqualTo(700);
380 assertThat(bs.contains(2)).isFalse();
381
382 bs = bs.remove(700);
383 assertThat(bs.isEmpty()).isTrue();
384
385 }
386
387 @Test
388 public void testFactories() {
389 assertThat(BitSet.of(7).contains(7)).isTrue();
390 assertThat(BitSet.of(77).contains(77)).isTrue();
391 assertThat(BitSet.of(777).contains(777)).isTrue();
392 assertThat(BitSet.ofAll(List.of(1).toJavaStream())).isEqualTo(BitSet.of(1));
393 assertThat(BitSet.fill(1, () -> 1)).isEqualTo(BitSet.of(1));
394 assertThat(BitSet.tabulate(1, i -> 1)).isEqualTo(BitSet.of(1));
395 }
396
397 @Test
398 public void shouldAllAll() {
399 assertThat(BitSet.empty().add(7).addAll(List.of(1, 2))).isEqualTo(BitSet.of(1, 2, 7));
400 assertThat(BitSet.empty().add(77).addAll(List.of(1, 2))).isEqualTo(BitSet.of(1, 2, 77));
401 assertThat(BitSet.empty().add(777).addAll(List.of(1, 2))).isEqualTo(BitSet.of(1, 2, 777));
402 }
403
404 @Test
405 public void shouldCollectInts() {
406 final Traversable<Integer> actual = java.util.stream.Stream.of(1, 2, 3).collect(BitSet.collector());
407 assertThat(actual).isEqualTo(of(1, 2, 3));
408 }
409
410 @Test
411 public void testEnums() {
412 BitSet<E> bs = BitSet.withEnum(E.class).empty();
413 bs = bs.add(E.V2);
414 assert bs.head() == E.V2;
415 bs = bs.add(E.V3);
416 assert bs.head() == E.V2;
417 bs = bs.remove(E.V2);
418 assert bs.head() == E.V3;
419 assert !bs.contains(E.V2);
420 assert bs.contains(E.V3);
421 }
422
423 @Test(expected = IllegalArgumentException.class)
424 public void shouldThrowAddNegativeElementToEmpty() {
425 BitSet.empty().add(-1);
426 }
427
428 @Test(expected = IllegalArgumentException.class)
429 public void shouldThrowAddNegativeElementToBitSet2() {
430 BitSet.empty().add(77).add(-1);
431 }
432
433 @Test(expected = IllegalArgumentException.class)
434 public void shouldThrowAddNegativeElementToBitSetN() {
435 BitSet.empty().add(777).add(-1);
436 }
437
438 @Test(expected = IllegalArgumentException.class)
439 public void shouldThrowAddNegativeElements() {
440 BitSet.empty().addAll(List.of(-1));
441 }
442
443 @Test(expected = IllegalArgumentException.class)
444 public void shouldThrowContainsNegativeElements() {
445 BitSet.empty().contains(-1);
446 }
447
448 @Test
449 public void shouldSerializeDeserializeNativeBitSet() {
450 final Object actual = deserialize(serialize(BitSet.of(1, 2, 3)));
451 final Object expected = BitSet.of(1, 2, 3);
452 assertThat(actual).isEqualTo(expected);
453 }
454
455 @Test
456 public void shouldSerializeDeserializeEnumBitSet() {
457 final Object actual = deserialize(serialize(BitSet.withEnum(E.class).of(E.V1, E.V2)));
458 final Object expected = BitSet.withEnum(E.class).of(E.V1, E.V2);
459 assertThat(actual).isEqualTo(expected);
460 }
461
462 @Test
463 public void shouldBehaveExactlyLikeAnotherBitSet() {
464 for (int i = 0; i < 10; i++) {
465 final Random random = getRandom(-1);
466
467 final java.util.BitSet mutableBitSet = new java.util.BitSet();
468 BitSet<Integer> functionalBitSet = BitSet.empty();
469
470 final int size = 5_000;
471 for (int j = 0; j < size; j++) {
472
473 if (random.nextInt() % 3 == 0) {
474 assertMinimumsAreEqual(mutableBitSet, functionalBitSet);
475
476 final int value = random.nextInt(size);
477 mutableBitSet.set(value);
478 functionalBitSet = functionalBitSet.add(value);
479 }
480
481 assertMinimumsAreEqual(mutableBitSet, functionalBitSet);
482
483
484 if (random.nextInt() % 5 == 0) {
485 if (!mutableBitSet.isEmpty()) { mutableBitSet.clear(mutableBitSet.nextSetBit(0)); }
486 if (!functionalBitSet.isEmpty()) { functionalBitSet = functionalBitSet.tail(); }
487
488 assertMinimumsAreEqual(mutableBitSet, functionalBitSet);
489 }
490 }
491
492 final Collection<Integer> oldValues = mutableBitSet.stream().sorted().boxed().collect(toList());
493 final Collection<Integer> newValues = functionalBitSet.toJavaList();
494 assertThat(oldValues).isEqualTo(newValues);
495 }
496 }
497
498 private void assertMinimumsAreEqual(java.util.BitSet oldSet, BitSet<Integer> newSet) {
499 assertThat(oldSet.isEmpty()).isEqualTo(newSet.isEmpty());
500 if (!newSet.isEmpty()) {
501 assertThat(oldSet.nextSetBit(0)).isEqualTo(newSet.head());
502 }
503 }
504
505
506
507 @Override
508 @Test
509 public void shouldConvertToSortedSetWithoutComparatorOnComparable() {
510 final Value<Integer> value = BitSet.of(3, 7, 1, 15, 0);
511 final Set<Integer> set = value.toSortedSet();
512 if (value.isSingleValued()) {
513 assertThat(set).isEqualTo(TreeSet.of(3));
514 } else {
515 assertThat(set).isEqualTo(TreeSet.of(0, 1, 3, 7, 15));
516 }
517 }
518
519
520
521 @Test
522 @Override
523 public void shouldConvertToPriorityQueueUsingImplicitComparator() {
524 final Value<Integer> value = BitSet.of(1, 3, 2);
525 final PriorityQueue<Integer> queue = value.toPriorityQueue();
526 if (value.isSingleValued()) {
527 assertThat(queue).isEqualTo(PriorityQueue.of(1));
528 } else {
529 assertThat(queue).isEqualTo(PriorityQueue.of(1, 2, 3));
530 }
531 }
532
533 @Test
534 @Override
535 public void shouldConvertToPriorityQueueUsingExplicitComparator() {
536 final Comparator<Integer> comparator = Comparator.naturalOrder();
537 final Value<Integer> value = BitSet.of(1, 3, 2);
538 final PriorityQueue<Integer> queue = value.toPriorityQueue(comparator);
539 if (value.isSingleValued()) {
540 assertThat(queue).isEqualTo(PriorityQueue.of(comparator, 1));
541 } else {
542 assertThat(queue).isEqualTo(PriorityQueue.of(comparator, 1, 2, 3));
543 }
544 }
545
546
547
548 private static class Mapper<T> implements Serializable {
549
550 private static final long serialVersionUID = 1L;
551
552 private final java.util.Map<Integer, T> fromIntMap = new java.util.HashMap<>();
553 private final java.util.Map<T, Integer> toIntMap = new java.util.HashMap<>();
554 private int nextValue = 0;
555
556 synchronized T fromInt(Integer i) {
557 if (i < nextValue) {
558 return fromIntMap.get(i);
559 } else {
560 throw new RuntimeException();
561 }
562 }
563
564 synchronized Integer toInt(T value) {
565 Integer i = toIntMap.get(value);
566 if (i == null) {
567 i = nextValue++;
568 toIntMap.put(value, i);
569 fromIntMap.put(i, value);
570 }
571 return i;
572 }
573 }
574 }